#include <iostream>
#include <fstream>
#include <vector>
#include <string>

using namespace std;

// 生成n位的Gray码序列
vector<string> generate_gray_code(int n) {
    if (n == 1) {
        return {"0", "1"};
    }

    // 递归生成n-1位的Gray码序列
    vector<string> prev_gray_code = generate_gray_code(n - 1);
    vector<string> gray_code;

    // 在n-1位的Gray码序列的每个元素前面加上0，组成n位的Gray码序列的前半部分
    for (string code : prev_gray_code) {
        gray_code.push_back("0" + code);
    }

    // 在n-1位的Gray码序列的每个元素逆序前面加上1，组成n位的Gray码序列的后半部分
    for (int i = prev_gray_code.size() - 1; i >= 0; i--) {
        gray_code.push_back("1" + prev_gray_code[i]);
    }

    return gray_code;
}

int main() {
    int n;
    
    // 从输入文件读取n
    ifstream input_file("input.txt");
    if (input_file.is_open()) {
        input_file >> n;
        input_file.close();
    } else {
        cout << "无法打开输入文件" << endl;
        return 1;
    }

    // 生成Gray码
    vector<string> gray_code = generate_gray_code(n);

    // 将结果输出到文件
    ofstream output_file("output.txt");
    cout << "生成Gray码:" << endl;
    if (output_file.is_open()) {
        for (string code : gray_code) {
            output_file << code << endl;
            cout << code << endl;
        }
        cout << "已写入文件output.txt" << endl;
        output_file.close();
    } else {
        cout << "无法打开输出文件" << endl;
        return 1;
    }

    return 0;
}